//Given a string array words, return the maximum value of length(word[i]) *
//length(word[j]) where the two words do not share common letters. If no such two 
//words exist, return 0. 
//
// 
// Example 1: 
//
// 
//Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
//Output: 16
//Explanation: The two words can be "abcw", "xtfn".
// 
//
// Example 2: 
//
// 
//Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
//Output: 4
//Explanation: The two words can be "ab", "cd".
// 
//
// Example 3: 
//
// 
//Input: words = ["a","aa","aaa","aaaa"]
//Output: 0
//Explanation: No such pair of words.
// 
//
// 
// Constraints: 
//
// 
// 2 <= words.length <= 1000 
// 1 <= words[i].length <= 1000 
// words[i] consists only of lowercase English letters. 
// 
// Related Topics 位运算 数组 字符串 👍 307 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;

public class P318MaximumProductOfWordLengths {
    public static void main(String[] args) {
        Solution solution = new P318MaximumProductOfWordLengths().new Solution();
        System.out.println(solution.maxProduct(new String[]{"eae", "ea", "aaf", "bda", "fcf", "dc", "ac", "ce", "cefde", "dabae"}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(String[] words) {
            int length = words.length;
            int[] masks = new int[length];
            for (int i = 0; i < length; i++) {
                String word = words[i];
                int wordLength = word.length();
                for (int j = 0; j < wordLength; j++) {
                    masks[i] |= 1 << (word.charAt(j) - 'a');
                }
            }
            int maxProd = 0;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    if ((masks[i] & masks[j]) == 0) {
                        maxProd = Math.max(maxProd, words[i].length() * words[j].length());
                    }
                }
            }
            return maxProd;
        }

        public int maxProduct1(String[] words) {
            Arrays.sort(words, Comparator.comparingInt(String::length));
            int max = 0;
            for (int i = words.length - 1; i >= 1; i--) {
                String cur = words[i];
                for (int j = i - 1; j >= 0; j--) {
                    String pre = words[j];
                    boolean noDup = true;
                    for (int k = 0; k < pre.length(); k++) {
                        if (cur.contains(pre.charAt(k) + "")) {
                            noDup = false;
                            break;
                        }
                    }
                    if (noDup) {
                        max = Math.max(cur.length() * pre.length(), max);
                    }
                }


            }
            return max;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
